package LeetCode.leetcode;

/**
 * @author: leiwenkang
 * @date: 2020/7/11
 * @time: 23:29
 */
public class Test215数组中的第K个最大元素 {
    public static void main(String[] args) {
        Test215数组中的第K个最大元素 solution = new Test215数组中的第K个最大元素();
        int[] nums = {3,2,1,5,6,4};
        System.out.println(solution.findKthLargest(nums, 2));
    }
    //快排的思路
    public int findKthLargest(int[] nums, int k) {
        int low = 0;
        int high = nums.length - 1;

        //倒数第k个，也就是正数第nums.length - k个
        int position = nums.length - k;
        while (low <= high) {
            int pos = partition(nums, low, high);
            if (pos == position) {
                return nums[pos];
            } else if (pos < position) {
                low = pos + 1;
            } else {
                high = pos - 1;
            }
        }
        throw new RuntimeException("不存在");
    }

    //从小到大排序
    private int partition(int[] nums, int low, int high) {
        if (low >= high) {
            return low;
        }
        int val = nums[low];
        while (low < high) {
            while (low < high && nums[high] >= val) {
                high--;
            }
            nums[low] = nums[high];

            while (low < high && nums[low] <= val) {
                low++;
            }
            nums[high] = nums[low];
        }

        nums[low] = val;
        return low;
    }
}
